package com.xyj.week01;

import java.util.Arrays;

/**
 * 数组归并排序
 */
public class T3 {

    public static void main(String[] args) {
        int[] arr = {8, 9, 2, 5, 3, 2, 1, 4, 5};
        System.out.println("排序前："+ Arrays.toString(arr));
        process(arr,0,arr.length-1);
        System.out.println("排序后："+Arrays.toString(arr));
    }


    /**
     * 递归处理--左右分为两部分  先分 然后再合并
     */
    public static void process(int []arr,int L,int R){
        if (L==R){
            return;
        }
        int mid = L + ((R-L)>>1);
        process(arr,L,mid);
        process(arr,mid+1,R);
        mergeSort(arr,L,mid,R);
    }

    /**
     * 归并排序  有序的两组数组进行排序
     * 新建一个help数组，
     * 两个排序好的依次从头往后进行比较
     * 如果哪个数小，就将这个数放到help数组中，
     * 直到其中一个数组的数全部被放入help数组
     * 然后将另一个还有数的数组全部放到help数组的后面
     * 最后将数组copy
     * @param arr 数组
     * @param l   左索引处
     * @param mid 中点
     * @param r  右索引处
     */
    private static void mergeSort(int[] arr, int l, int mid, int r) {
        //辅助数组
        int[] help =new int[r-l+1];
        int i=0;
        int p1=l;
        int p2=mid+1;
        //左数组和右数组索引同时右边移 从小到大排序
        while(p1<=mid&&p2<=r){
            help[i++]= arr[p1]> arr[p2] ? arr[p2++] : arr[p1++];
        }
        //要么左边的排完了
        while (p2<=r){
            //将右边数组的剩余数都放入help数组
            help[i++]=arr[p2++];
        }
        //要么右边的排完了
        while(p1<=mid){
            //将右边数组的剩余数都放入help数组
            help[i++]=arr[p1++];
        }
        //数组copy
        for (i = 0; i < help.length; i++) {
            arr[l+i]=help[i];
        }
    }


}

